package 剑指offer;

import java.util.HashMap;

public class _35复杂链表的复制 {
	/**
	 * 
	 *@time 2021年3月3日下午3:47:19
	 * 
	 *@param head
	 *@return Node
	 *
	 *@see哈希表
	 */
    public Node copyRandomList1(Node head) {
    	if(head==null)  return null;
    	HashMap<Node, Node> map=new HashMap<Node, Node>();
    	Node cur = head;
    	while(cur!=null) {
    		map.put(cur,new Node(cur.val));
    		cur=cur.next;
    	}
    	cur = head;
    	while(cur!=null) {
    		map.get(cur).next = map.get(cur.next);
    		map.get(cur).random = map.get(cur.random);
    	}
		return map.get(head);       
    }
    /**
     * 
     *@time 2021年3月3日下午3:59:14
     * 
     *@param head
     *@return Node
     *
     *@see拼接+拆分
     */
    public Node copyRandomList2(Node head) {
    	if(head==null)  return null;
    	Node cur = head;
    	//复制一份新的Node,并拼接起来
    	while(cur != null) {
    		Node temp = new Node(cur.val);
    		temp.next = cur.next;
    		cur.next = temp;
    		cur = temp.next;
    	}
    	cur = head;
    	//将random放入到新的节点中
    	while(cur != null) {
    		if(cur.random != null) 
    			cur.next.random = cur.random.next; 
    		
    		cur = cur.next.next;
    	}
    	//将节点弄成两个链表
    	cur = head;
    	
    	Node resNode = head.next;
    	Node tNode = head.next;
    	while(tNode.next !=null) {
    		cur.next =cur.next.next;
    		tNode.next = tNode.next.next;  	
    		cur = cur.next;
    		tNode = tNode.next;
    	}
    	cur.next = null;
		return resNode;
    	
    }
    /**
     * 
     *@time 2021年3月3日下午4:44:19
     * 
     *@param head
     *@return Node
     *
     *@see 拼接
     */
    public Node copyRandomList3(Node head) {
    	
		return head;
    	
    }
}
